Problema del viatjant de comerç
Suposem que se’ns dona una instància del Problema del Viatjant de Comerç (\mathtt{TSP}) amb n ciutats i distàncies d_{ij}. Per a cada subconjunt S de les ciutats excloent la ciutat 1, i per a cada j \in S, definim c[S,j] com el camí més curt que comença a la ciutat 1, visita totes les ciutats de S i acaba a la ciutat j.
Doneu un algorisme que calculi c[S,j] mitjançant programació dinàmica, és a dir, progressant de conjunts S més petits a conjunts més grans i utilitzant una definició recurrent de c[S,j]. Mostreu que aquest algoritme resol el \mathtt{TSP} en temps O(n^2 2^n). Quins són els requeriments d’espai de l’algoritme?
Suposem que volem trobar el camí més curt (en el sentit de la suma dels pesos) de 1 a n, sense necessitat de visitar totes les ciutats. Argumenteu per què aquest problema es pot resoldre en temps polinòmic.